Cryptography systems are commonly used for providing secret communication of a text message or a cryptographic “key,” or for authenticating identity of a sender via a digital signature. Once encoded, information is generally stored in a computer file (on a disk, for example) or transmitted to a desired recipient. So-called “public key cryptography” uses two asymmetric “keys,” or large numbers, consisting of a public key and private key pair. If the public key is used to encode information according to a known algorithm, then the private key is usually needed by the recipient to decode that information, and vice-versa. Public key cryptography relies upon complex mathematical functions by which the public and private keys are related, such that it is extremely difficult to derive the private key from the public key, even with today's high speed processing computers.
One type of public key cryptography system is based upon elliptic curve representations and related mathematics and processing. As an end product of such processing, at least one coded block of information is created and represented as a data point having both X and Y coordinates, with each coordinate being a number between zero and 2N−1; if a large quantity of information is to be enciphered, there may be many such points, each point represented by at least 2N bits of information.
In these cryptographic systems, a finite field is also chosen, i.e., F2N, where N denotes the number of binary bits used by a computer to represent an element of the finite field. An irreducible generator polynomial or order N is then selected which defines the arithmetic operations in the field. The coefficients of an equation defining an elliptic curve are then selected, and a point P (having X and Y coordinates) on the elliptic curve. Once these terms are chosen, a point addition operation is defined, and from it a point multiplication operation is thereby defined,kP=P+P+P+ . . . +P(k times)i.e., P is added to itself k−1 times. With these terms, a private key consisting of one number, such as the number k, and a public key consisting of the product of the point P and the private key (the product being constrained by the finite field and the elliptic curve chosen) may be selected and used for public key cryptographic applications.
Multiplication or, more precisely, scalar multiplication is the dominant operation in elliptic curve cryptography. The speed at which multiplication can be done determines the performance of an elliptic curve method. Multiplication of a point P on an elliptic curve by an integer k may be realized by a series of additions (i.e., k*P=P+P+ . . . +P, where the number of Ps is equal to k). This is very easy to implement in hardware since only an elliptic adder is required, but it is very inefficient. That is, the number of operations is equal to k which may be very large.
The classical approach to elliptic curve multiplication is a double and add approach. For example, if a user wishes to realize k*P, where k=25 then 25 is first represented as a binary expansion of 25. That is, 25 is represented as a binary number 11001. Next, P is doubled a number of times equal to the number of bits in the binary expansion minus 1. For ease in generating an equation of the number of operations, the number of doubles is taken as m rather than m−1. The price for simplicity here is being off by 1. In this example, the doubles are 2P, 4P, 8P, and 16P. The doubles correspond to the bit locations in the binary expansion of 25 (i.e., 11001), except for the 1s bit. The doubles that correspond to bit locations that are then added along with P if the is bit is a 1. The number of adds equals the number of 1s in the binary expansion. In this example, there are three additions since there are three 1s in the binary expansion of 25 (i.e., 11001). So, 25P=16P+8P+P.
On average, there are m/2 1s in k. This results in m doubles and m/2 additions for a total of 3m/2 operations. Since the number of bits in k is always less than the value of k, the double and add approach requires fewer operations than does the addition method described above. Therefore, the double and add approach is more efficient (i.e., faster) than the addition approach.
While working on an elliptic curve allows smaller parameters relative to a modular arithmetic based system offering the same security, some of the efficiency advantage of smaller parameters is offset by the added complexity of doing arithmetic on an elliptic curve as opposed to ordinary modular arithmetic. For purposes of determining efficiency, elliptic doubles and elliptic additions are often grouped and considered elliptic operations. To gain even more efficiency advantages by going to elliptic curves, cryptographers seek ways to reduce the cost of an elliptic curve operation, or reduce the number of elliptic operations required. An elliptic curve method that requires fewer operations, or more efficiently executable operations, would result in an increase in the speed, or performance, of any device that implements such a method.
Additionally, the double and add approach is susceptible to a power analysis attack (PAA). It became clear that the implementation of a public key enciphering algorithm of the elliptical curve type on a smart card was vulnerable to attacks consisting of a differential analysis of current consumption making it possible to find the private deciphering key. These attacks are known as a Differential Power Analysis (DPA) attacks. The principle of these DPA attacks is based on the fact that the current consumption of the microprocessor executing the instructions varies according to the data item being manipulated.
The foregoing “background” description is for the purpose of generally presenting the context of the disclosure. Work of the inventor, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly or impliedly admitted as prior art against the present invention. The foregoing paragraphs have been provided by way of general introduction, and are not intended to limit the scope of the following claims. The described embodiments, together with further advantages, will be best understood by reference to the following detailed description taken in conjunction with the accompanying drawings.